【LeetCode 784】Letter Case Permutation字母大小写全排列

发表于 | 分类于

[LeetCode 784]Letter Case Permutation字母大小写全排列

问题描述:

给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

示例:

1
2
3
4
5
6
7
8
9
示例:
输入: S = "a1b2"
输出: ["a1b2", "a1B2", "A1b2", "A1B2"]

输入: S = "3z4"
输出: ["3z4", "3Z4"]

输入: S = "12345"
输出: ["12345"]

注意：

S 的长度不超过12。
S 仅由数字和字母组成。

Solution:

Solution : 深度优先搜索即可解决

Code:

beat 84%
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
  public static List<String> letterCasePermutation (String S) {
        List<String> res = new ArrayList<>();
        letterCasePermutationHelper(res, S, 0, new StringBuilder());
        return res;
    }

    private static void letterCasePermutationHelper (List<String> list, String s, int pos, StringBuilder sb) {
        for (int i = pos; i < s.length(); i++) {
            if ('0' <= s.charAt(i) && s.charAt(i) <= '9')
                sb.append(s.charAt(i));
            else{
            		//添加原来的字母
                sb.append(s.charAt(i));
                StringBuilder t = new StringBuilder(sb.toString());
                letterCasePermutationHelper(list, s, i + 1, sb);
                sb = t;
                //添加转变后的字母
                sb.deleteCharAt(i);
                sb.append(transLeeterCase(s.charAt(i)));
            }
        }
        list.add(sb.toString());
    }

    private static char transLeeterCase (char letter) {
        char res = ' ';
        if ('a' <= letter && letter <= 'z') {
            res = (char) (letter-('a'-'A'));
        } else if ('A' <= letter && letter <= 'Z') {
            res = (char) (letter+'a'-'A');
        }
        return res;
    }
}
Thanks!